
// 1. 定义一个类型表示树中的节点
#include <iostream>

using namespace std;
class Node {
public:
  int value;
  Node *l;
  Node *r;

  Node(int num) {
    value = num;
    l = nullptr;
    r = nullptr;
    cout << "A Node is created." << endl;
  }
};

// 2. 定义一个类型表示整棵树
class BinaryTree {
public:
  Node *root;

  BinaryTree(Node *r = nullptr) {
    root = r;
  }

  // 从节点 p 开始遍历二叉树
  void dfs(Node *p) {
    if (p == nullptr) {
      return;
    }

    cout << p->value << endl; // 先访问当前节点

    dfs(p->l);
    dfs(p->r);
  }

  void preorder() {
    dfs(root);
  }

  // # Homework 0304
  // 使用非递归方法实现 preorder 遍历
  void preorder_nonrecursive() {
    // ...
  }
};

